package arithmetic.demo6;

import java.util.PriorityQueue;
import java.util.Random;


/**
 * 题目： 分冶_排序数组
 */

class Solution1 {


    // 快速排序
    public int[] sortArray(int[] nums) {
        int n = nums.length;



        
        // 开始递归
        quickSort( nums ,0, n - 1);

        return nums;
    }

    private void quickSort(int[] nums, int left , int right) {
        // 递归出口
        if(left >= right) {
            return; 
        }

        // 随机数获取 key 的值
        Random r = new Random();
        int index =  r.nextInt(right - left + 1)  + left;
        int key = nums[index];
        int begin = left -1,  end = right +1 , i = left; 

        // 开始数组三段法 
        while(i < end) {
            if(nums[i] > key) {
                swap(nums, --end, i);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(nums, ++begin , i++);
            }
        }

        Random r1 = new Random();
       


        quickSort(nums, left, begin);

        quickSort(nums, end ,right);
    }



    // 交换
    private void swap(int[] nums , int i , int j ) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;



    }

}


/**
 * 排序_数组中第k个大的元素
 */

class Solution2 {
    public int findKthLargest(int[] nums, int k) {

        // 定义一个小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)-> {
            return a-b;
        });



        // 加入队列
        for(int i =0; i < k ; i++) {
            queue.add(nums[i]);
        }

        // 调整队列
        for(int i = k; i < nums.length; i++) {
            int num = queue.peek();
            if(nums[i] >= num) {
                queue.poll();
                queue.add(nums[i]);
            }
        }

        // 返回第k 个最大 也是小根堆中的底部元素
        return queue.poll();
    }
}


/**
 * 题目： 库存管理（三）
 */


class Solution3 {
    public int[] inventoryManagement(int[] stock, int cnt) {
        // 存储结果
        int[] ret = new int[cnt];

        if (stock.length == 0 || cnt == 0) {
            return ret;
        }

        // 定义一个小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> {
            return a-b;
        });

        // 加入队列
        for (int i = 0; i < stock.length; i++) {
            queue.add(stock[i]);
        }


        // 将最小值放入队列
        for (int i = 0; i < cnt; i++) {
            ret[i] = queue.poll();
        }

        return ret;
    }
}


/**
 * 分治-快排_快速选择算法
 */

class Solution {
    int ret ;
    public int findKthLargest(int[] nums, int k) {

        // 进行快速排序
        // 从大往小排序
        qSelect(nums, 0 , nums.length-1 , k);

        return ret;

    }

    private void qSelect(int[] nums, int bagin, int end, int dk) {

        // 随机数生成 key
        Random r = new Random();
        int index = r.nextInt(end - bagin + 1) + bagin;
        int key = nums[index];

        // 定义三指针
        int left = bagin -1, right = end + 1, i = bagin;

        // 数组三段排序法
        while(i < right) {
            if(nums[i] < key) {
                swap(nums, ++left,i++);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(nums, --right , i);
            }
        }

        int c = end - right + 1;
        int b = (right - 1)  - (left + 1) + 1;
        int a = left - bagin + 1;


        if( c >= dk) {
            // 右区域排序
            qSelect(nums, right , end, dk);
        } else if( b + c >= dk) {
            ret =nums[right -1];
            return;
        } else {
            // 左区域排序
            qSelect(nums, bagin , left,dk - b - c);
        }






    }

    // 交换
    private void swap(int[] nums , int i , int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

/**
 * 分治-归并_归并排序
 */

class Solution4 {
    int[] ret ;
    public int[] sortArray(int[] nums) {
        ret = new int[nums.length];
        // 归并排序
        merSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void merSort(int[] nums, int bagin , int end) {
        if(end <= bagin) {
            return;
        }

        // 确认中间值
        int mid = (bagin  + end)/2;

        // 左区域
        merSort(nums,bagin, mid);
        // 右区域
        merSort(nums,mid+1, end);

        int left = bagin;
        int right =  mid+1;
        int i = 0;
        int[] tmp = new int[end - bagin +1];

        //  进行合并
        while(left <= mid && right <= end ) {

            if(nums[left] <= nums[right]) {
                tmp[i++] = nums[left++];
            }  else {
                tmp[i++] = nums[right++];
            }
        }

        while(right <= end) {
            tmp[i++] = nums[right++];
        }

        while(left <= mid) {
            tmp[i++] = nums[left++];
        }

        // 进行拷贝
        // 注意这里要从 left 开始
        for(int j = bagin; j <= end  ; j++) {
            nums[j] = tmp[j-bagin] ;
        }

    }
}